package cn.edu.zxj.day_2024_10_21;

/**
 * Created with IntelliJ IDEA.
 * Description：模式实现HashMap, 支持 put, get, remove
 *
 * @author: zxj
 * @date: 2024-10-21
 * @time: 14:46:40
 */
public class MyHashMap<K, V> {
    /*
     * 定义结点类
     */
    private static class Node<K, V> {
        K key;
        V value;
        Node<K, V> next;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public Node(K key, V value, Node<K, V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    // 默认容量
    private static final int DEFAULT_CAPACITY = 1 << 4;
    // 默认负载因子
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 容量
    private int size;
    // 桶数组
    private Node<K, V>[] table;

    /*
     默认构造
     */
    public MyHashMap() {
        this(DEFAULT_CAPACITY);
    }

    public MyHashMap(int capacity) {
        this.table = new Node[capacity];
        this.size = 0;
    }

    /*
     * 获取值
     */
    public V get(K key) {
        int index = getIndex(key, table.length);
        Node<K, V> node = table[index];
        while (node != null) {
            if (node.key.equals(key)) {
                return node.value;
            }
            node = node.next;
        }
        return null;
    }

    /*
     * 添加元素
     */
    public void put(K key, V value) {
        int index = getIndex(key, table.length);
        Node<K, V> node = table[index];
        Node<K, V> prev = null;
        while (node != null) {
            if (node.key.equals(key)) {
                node.value = value;
                return;
            }
            prev = node;
            node = node.next;
        }
        // 尾插法
        if (prev == null) {
            table[index] = new Node<>(key, value);
        } else {
            prev.next = new Node<>(key, value);
        }
        size++;

        // 判断是否需要扩容
        if (size > table.length * DEFAULT_LOAD_FACTOR) {
            resize();
        }

    }

    public void remove(K key) {
        if (size == 0) {
            return;
        }
        int index = getIndex(key, table.length);
        Node<K, V> node = table[index];
        Node<K, V> prev = null;
        while (node != null) {
            if (node.key.equals(key)) {
                if (prev == null) {
                    table[index] = node.next;
                } else {
                    prev.next = node.next;
                }
                size--;
                return;
            }
            prev = node;
            node = node.next;
        }
    }


    private void resize() {
        Node<K, V>[] oldTable = table;
        table = new Node[oldTable.length << 1];
        size = 0;
        for (Node<K, V> node : oldTable) {
            while (node != null) {
                put(node.key, node.value);
                node = node.next;
            }
        }
    }


    private int getIndex(K key, int length) {
        int hashCode = key.hashCode();
        // 取模运算
        return Math.abs(hashCode % length);
    }

}
